package com.zhugang.week09;

/**
 * @program algorithms
 * @description: floodFill
 * @author: chanzhugang
 * @create: 2022/08/22 22:43
 */
public class FloodFill {

    /**
     * 面试题 08.10 颜色填充
     * 连通性问题
     *
     * @param image
     * @param sr
     * @param sc
     * @param newColor
     * @return
     */
    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        // 周围区域颜色相同，填充为新颜色
        // 图上的DFS
        int n = image.length;
        int m = image[0].length;
        dfs(image, n, m, sr, sc, image[sr][sc], newColor);
        return image;
    }

    private void dfs(int[][] image, int n, int m, int sr, int sc, int color, int newColor) {
        image[sr][sc] = newColor;
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        for (int i = 0; i < 4; i++) {
            int newr = sr + dirs[i][0];
            int newc = sc + dirs[i][1];
            if (newr < 0 || newr >= n || newc < 0 || newc >= m || image[newr][newc] != color || image[newr][newc] == newColor) {
                // 新节点颜色不同于原颜色， 遍历过的 排除
                continue;
            }
            dfs(image, n, m, newr, newc, color, newColor);
        }
    }
}